//
//  LinkListExt.hpp
//  DataStructure
//
//  Created by 舒磊明 on 2020/6/22.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef LinkListExt_hpp
#define LinkListExt_hpp

#include <stdio.h>
#include <iostream>
#include "LinkList.hpp"

// 删除不带头节点单链表中所有x的结点
void removex(LinkList &L, int x);

// 带头结点，删除值为x的结点
void removeX2(LinkList &L, int x);

// 带头结点，反向输出
void reversePrint(LinkList L);

// 带头结点，删除最小值
void delMin(LinkList &L);

// 带头节点，逆序
void reverse(LinkList &L);

// 带头结点，递增
void orderList(LinkList &L);

// 带头结点，删除值在s～t之间的结点
void rangeDel(LinkList &L, int s, int t);

// 找出公共结点
LinkList commonNode(LinkList L1, LinkList L2);

// 带头节点，递增输出并释放元素
void printAndFree(LinkList &L);

// 带头节点，A拆分为A和B，A包含奇数号元素，B包含偶数号元素，顺序不变
void splitList(LinkList L);

// C={a1 b1 a2 b2 ... an bn} => A = {a1 a2 ...}, B = {bn ... b2 b1}
void splitList2(LinkList L);

// 带头节点的递增的单链表，删除重复的元素
void DelRepeat(LinkList &L);

// 两个递增的单链表，合并为递减的单链表。要求使用原节点合并
void mergeList(LinkList &L1, LinkList &L2, LinkList L);

// A，B为递增单链表，用公共节点创建C。不破坏A和B
void mergeCommom(LinkList L1, LinkList L2);

// A,B为递增单链表，求交集，并存放于A中
void intersection(LinkList &L1, LinkList &L2);

/*------------------------------------------------*/
/*能否用更好的方法实现？------------------------------*/
// A=a1,a2...an, B=b1,b2...bm；判断B是否为A的子序列。
bool isSubList(LinkList L1, LinkList L2);
/*------------------------------------------------*/
/*------------------------------------------------*/

// 判断循环双链表是否对称
typedef struct Lnode {
    int data;
    struct Lnode *prior, *next;
} DLnode, *DLinkList;
bool isMirror(DLinkList L);

// 2个循环单链表L1和L2，将L2链到L1上后，依然为单链表
void mergeLoopList(LinkList &L1, LinkList &L2);

// 带头节点，循环单链表，data为正整数，找出最小值，删除输出。直到表为空，最后删除头节点。
void PrintAndDelete(LinkList &L);

// 非循环双链表，访问一次freq+1，并保持按照freq递减排序。
typedef struct FDNode {
    int data, freq;
    struct FDNode *pred, *next;
} FDNode, *FDLinkList;

FDNode* Locate(FDLinkList L, int x);

// 带头节点单链表，找到倒数第k个位置上的元素，如果查找成功，输出data，返回1，否则返回0
bool searchElem(LinkList L, int k);

// 带头节点的单链表保存单词，如果有相同后缀则共享后缀。
// str1和str2分别指向两个单链表头节点，请高效地找到同节点的起始位置
LNode* searchExt(LinkList str1, LinkList str2);

// 单链表保存m个数，|data| <= n
// 高效算法对于绝对值相同的节点，只保留第一个
void removeNumber(LinkList &L, int n);

// 判断链表是否有环，若有则返回环的入口
LNode* findLoop(LinkList L);

// 带头节点单链表，L={a1,a2...an} -> L={a1,an,a2,an-1,a3,an-2...}
// 要求S(1)并且高效
void ListSort(LinkList &L);

#endif /* LinkListExt_hpp */
